/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumSum = function (grid) {
  // 收集所有1的位置
  const ones = [];
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === 1) {
        ones.push([i, j]);
      }
    }
  }

  // 如果只有3个1，直接返回3（每个1一个1x1的矩形）
  if (ones.length === 3) return 3;

  let minTotalArea = Infinity;

  // 计算覆盖一组点的最小矩形面积
  const getArea = (points) => {
    if (points.length === 0) return 0;
    let minRow = Infinity,
      maxRow = -Infinity;
    let minCol = Infinity,
      maxCol = -Infinity;

    for (const [r, c] of points) {
      minRow = Math.min(minRow, r);
      maxRow = Math.max(maxRow, r);
      minCol = Math.min(minCol, c);
      maxCol = Math.max(maxCol, c);
    }

    return (maxRow - minRow + 1) * (maxCol - minCol + 1);
  };

  // 方法1: 按列划分成左、中、右三部分
  for (let c1 = 0; c1 < grid[0].length; c1++) {
    for (let c2 = c1 + 1; c2 < grid[0].length; c2++) {
      const left = [],
        mid = [],
        right = [];
      for (const [r, c] of ones) {
        if (c <= c1) left.push([r, c]);
        else if (c <= c2) mid.push([r, c]);
        else right.push([r, c]);
      }
      if (left.length > 0 && mid.length > 0 && right.length > 0) {
        const area = getArea(left) + getArea(mid) + getArea(right);
        minTotalArea = Math.min(minTotalArea, area);
      }
    }
  }

  // 方法2: 按行划分成上、中、下三部分
  for (let r1 = 0; r1 < grid.length; r1++) {
    for (let r2 = r1 + 1; r2 < grid.length; r2++) {
      const top = [],
        mid = [],
        bottom = [];
      for (const [r, c] of ones) {
        if (r <= r1) top.push([r, c]);
        else if (r <= r2) mid.push([r, c]);
        else bottom.push([r, c]);
      }
      if (top.length > 0 && mid.length > 0 && bottom.length > 0) {
        const area = getArea(top) + getArea(mid) + getArea(bottom);
        minTotalArea = Math.min(minTotalArea, area);
      }
    }
  }

  // 方法3: 先垂直划分，再水平划分
  for (let c = 0; c < grid[0].length; c++) {
    const left = [],
      right = [];
    for (const [r, col] of ones) {
      if (col <= c) left.push([r, col]);
      else right.push([r, col]);
    }
    if (left.length === 0 || right.length === 0) continue;

    // 对左侧再水平划分
    for (let r = 0; r < grid.length; r++) {
      const topLeft = [],
        bottomLeft = [];
      for (const [row, col] of left) {
        if (row <= r) topLeft.push([row, col]);
        else bottomLeft.push([row, col]);
      }
      if (topLeft.length > 0 && bottomLeft.length > 0 && right.length > 0) {
        const area = getArea(topLeft) + getArea(bottomLeft) + getArea(right);
        minTotalArea = Math.min(minTotalArea, area);
      }
    }

    // 对右侧再水平划分
    for (let r = 0; r < grid.length; r++) {
      const topRight = [],
        bottomRight = [];
      for (const [row, col] of right) {
        if (row <= r) topRight.push([row, col]);
        else bottomRight.push([row, col]);
      }
      if (left.length > 0 && topRight.length > 0 && bottomRight.length > 0) {
        const area = getArea(left) + getArea(topRight) + getArea(bottomRight);
        minTotalArea = Math.min(minTotalArea, area);
      }
    }
  }

  // 方法4: 先水平划分，再垂直划分
  for (let r = 0; r < grid.length; r++) {
    const top = [],
      bottom = [];
    for (const [row, c] of ones) {
      if (row <= r) top.push([row, c]);
      else bottom.push([row, c]);
    }
    if (top.length === 0 || bottom.length === 0) continue;

    // 对上方再垂直划分
    for (let c = 0; c < grid[0].length; c++) {
      const leftTop = [],
        rightTop = [];
      for (const [row, col] of top) {
        if (col <= c) leftTop.push([row, col]);
        else rightTop.push([row, col]);
      }
      if (leftTop.length > 0 && rightTop.length > 0 && bottom.length > 0) {
        const area = getArea(leftTop) + getArea(rightTop) + getArea(bottom);
        minTotalArea = Math.min(minTotalArea, area);
      }
    }

    // 对下方再垂直划分
    for (let c = 0; c < grid[0].length; c++) {
      const leftBottom = [],
        rightBottom = [];
      for (const [row, col] of bottom) {
        if (col <= c) leftBottom.push([row, col]);
        else rightBottom.push([row, col]);
      }
      if (top.length > 0 && leftBottom.length > 0 && rightBottom.length > 0) {
        const area = getArea(top) + getArea(leftBottom) + getArea(rightBottom);
        minTotalArea = Math.min(minTotalArea, area);
      }
    }
  }

  return minTotalArea;
};
